package 算法.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/
 * @author lchenglong
 * @date 2022/4/21
 */
public class Offer13 {

    public static void main(String[] args) {
        Offer13 instance = new Offer13();
        int ans = instance.movingCount(11, 8, 16);
        System.out.println(ans);
    }
    public int movingCount(int m, int n, int k) {
        if (k == 0) return 1;
        boolean[][] dp = new boolean[m][n];
        dp[0][0] = true;
        int count = 1;
        for(int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if ((i==0&&j==0)||get(i)+get(j)>k)continue;
                if (i-1>=0)dp[i][j]|=dp[i-1][j];
                if (j-1>=0)dp[i][j]|=dp[i][j-1];
                count+= dp[i][j]?1:0;
            }
        }
        return count;
    }
    int get(int x){
        int res = 0;
        while (x!=0){
            res+=x%10;
            x /=10;
        }
        return res;
    }
}
